Vào năm 1835, Moltke được phép nghỉ 6 tháng đi các nước Đông Nam Âu. Sau một khoảng thời gian ngắn ở Kostantiniyye – kinh đô đế quốc Thổ-Ottoman, ông được vua Mahmud II yêu cầu hỗ trợ canh tân quân đội Thổ. Chính quyền Berlin đã ban lệnh cho ông chấp thuận đề nghị này. Do vậy, Moltke ở lại Thổ trong vòng 4 năm tới;[14] trong thời gian này, ông học tiếng Thổ và khảo sát thành phố Konstantiniyye, các eo biển Vosporos và Dardanéllia. Ông còn đến Wallachia, Bulgaria, Rumelia, và đi nhiều chuyến hành trình ở cả hai bên eo biển Thổ Nhĩ Kỳ.[12] Ông đã cố vấn cho vua Thổ về nhiều vấn đề quân sự – từ việc xây thành đắp lũy và khai triển pháo binh cho tới việc xây dựng thêm đường thủy và đường bộ. Những lời khuyên của Moltke được người Thổ vui vẻ đón nhận, nhưng đó chỉ là ngoài mặt. Trên thực tế, họ rất ít thực hiện các đề xuất của ông.[14]

Vào năm 1838, khi tướng Hafiz Pasha nhận lệnh trấn áp cuộc "khởi loạn" của tổng đốc Ai Cập là Muhammad Ali, Moltke được vua Thổ bổ nhiệm làm tham tán – nói cách khác là tham mưu trưởng – của Hafiz Pasha. Moltke đến tổng hành dinh của Hafiz vào tháng 3 năm 1838 và nhận thấy tình hình tồi tệ của quân đội Thổ. Bị trải rộng trên một địa bàn quá rộng lớn, các lực lượng được trang bị và tổ chức kém của Thổ án ngữ tại các cứ điểm phòng thủ mỏng yếu và không được sự yểm trợ đầy đủ của pháo binh. Moltke liền bắt tay vào việc khảo sát địa hình và thăm dò tình trạng của từng đơn vị Thổ. Mặc dù bị sửng sốt trước những gì ông chứng kiến, Moltke đã đệ trình một kế hoạch tác chiến lên viên chỉ huy của mình. Ông quyết định tổ chức phòng ngự, dựa trên tình hình bi đát của quân đội Thổ và cái mà ông gọi là thiên hướng bị động của người Hồi giáo. Ông bài trí một kế hoạch nhằm tập kết một số lực lượng tại một cứ điểm phòng ngự vững chãi ở thành phố Biradschik dọc theo sông Euphrates và trừ bị phần lớn binh lực gần thị trấn Ufra.[14]

Việc chuẩn bị chiến dịch diễn ra khó nhọc trong mùa đông năm 1838 – 1839, khi mà khoảng 30–50% quân lực của Thổ đào ngũ hoặc là đổ bệnh. Tuy vậy, khi mùa xuân đến, quân đội Thổ dai sức mở đường tiến qua những ngọn đèo hiểm trở vẫn còn phủ đầy băng tuyết và hành binh trên những bình nguyên gồ ghề trong mưa gió để đến các vị trí phòng ngự đã được hoạch định của mình. Trong tay Hafix có 30 ngàn quân và 11 khẩu đại bác. Dựa theo đề xuất của Moltke, tướng Thổ triển khai một số binh lực tại một vị trí tiền tiêu gần thành phố biên giới Nezib. Phần còn lại của quân Thổ được bố trí ở khu vực thành phố Biradschik. Moltke còn khuyên tướng Thổ không nên xây cầu bắc qua sông Euphrates vì ông tin rằng binh lính không có đường rút sẽ chiến đấu ngoan cường hơn. Ngày 28 tháng 12, Muhammad Ali huy động 40 ngàn quân và 160 đại bác tràn qua biên giới. Quân Ai Cập hành binh theo đội hình dọc và bị kéo căng trên một mặt trận dài khoảng 129 km. Nắm bắt điều kiện thuận lợi này, tham tán Moltke khuyên Hafiz tổ chức tập kích vào đội hình sơ hở của địch, nhưng viên tướng Thổ từ chối. Hai ngày sau, quân Ai Cập vào được các vị trí tấn công của mình và tiến hành thám sát Biradschik. Quân Thổ đã đẩy lùi đối phương và Hafiz tin rằng mình đã thắng trận.[14]

Dù vậy, Moltke vẫn lo lắng. Ông nhận thấy quân Ai Cập đã bắt đầu di chuyển vào vị trí để phát động một cuộc tấn công vào sườn và phía sau thị trấn Nezib. Vì vậy, ông khuyên Hafiz tập trung pháo lực để phòng vệ hai bên sườn quân Thổ. Thế nhưng, dựa trên các điềm xấu, các cố vấn Hồi giáo của Hafiz khuyên ông ta không nên làm điều đó và một lần nữa, tướng Thổ không làm theo yêu cầu của Moltke. Moltke đành từ chức cố vấn quân sự của Hafiz Pasha và lãnh quyền chỉ huy pháo binh Thổ Nhĩ Kỳ[14]. Vào ngày 24 tháng 6 năm 1839, quân Ai Cập phá tan quân Thổ trong trận Nezib.[18] Nhờ sự chỉ huy khéo léo của Moltke, pháo binh Thổ gây được một số tổn thất cho địch và là binh chủng Thổ cuối cùng rút khỏi trận địa.[19] Sau thảm bại của quân đội Thổ, Moltke phải qua nhiều khó khăn mới về đến biển Đen, rồi từ đây ông về Konstantiniyye. Sau khi được tin người bảo trợ của mình là Mahmud II đã chết,[12] Moltke trở về Berlin vào tháng 12 năm 1838 trong tình trạng suy sụp sức khỏe và tinh thần. Nhưng, trước sự ngỡ ngàng của ông, Moltke được chào đón như một anh hùng và được Quốc vương trao tặng huân chương Thập tự Xanh cao quý nhất của quân đội Phổ.[11][14]

Sau này, Moltke đã xuất bản một số bức thư mà ông viết cho gia đình ông trong thời gian ở Thổ thành tuyển tập Những lá thư về các tình hình và sự kiện ở Thổ Nhĩ Kỳ trong những năm 1835 đến 1839 (Briefe über die Zustände und Begebenheiten in der Türkei 1835–39, 1841). Được đón nhận rộng rãi trong thời gian đó, tuyển tập được ca ngợi vì văn phong súc tích và cách miêu tả hấp dẫn về một đế quốc xa xôi.[12][20]